package leetcode.dfs;

import datastructure.tree.TreeNode;

/**
 * @Description:
 * @Author Ammar
 * @Create 2023/7/19 20:54
 */
public class Test {

    int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        max(root);
        return max;
    }
    public int max(TreeNode<Integer> node) {
        if (node == null) return 0;

        int left = Math.max(max(node.left), 0);
        int right = Math.max(max(node.right), 0);

        // 经过该节点的最大路径和
        max = Math.max(max, node.val + left + right);
        return node.val + Math.max(left, right);
    }

}
